package i_SegmentTree;


/**注意：2^k+? > 2^k; 你不能拿当2^(k-1)+? 和 2^k 比较，这是常有的思维误区，错位比较是无法一一对应的；
 * 
 * @author 
 * 
 * 区间树很重要的一点：线段树考虑的是既定范围内的更新和查询(涂色和看看是什么色)，所以采用静态数组，因此关于空间的计算是一个核心的点；线段树的范围可以分为两种情况：2^k or 介于幂之间，即2^k~2^(k+1)
 * 开辟多少空间呢？一个区间有n个元素，若n=2^k，则一定是一个满二叉树(因为区间长度每次都是二等分，满二叉树要求除了最后的长度1之外不出现奇数长度，即n=2^k),
 * 						则由于线段树的特性最后一行(全部拆封成单元素节点)的节点数就是n;结合满二叉树的性质，其前边所有行的节点树是n-1,则需要开辟2n-1个空间
 * n=2^k+?,则相当于在原满二叉树下加了一层，则这一层最多需要(2n-1)+1个空间，即总共需要4n-1个空间；
 *所以，如果精确一点分而治之，就分别按两种情况开辟空间；粗略一点，直接选最大值就可以hold住所有情况，即直接开辟4n-1个空间；
 *由于使用的是数组，所以要像堆一样表示父子关系，就需要形成完全二叉树，即最后一层有些空的叶子要占位来形成完全二叉树，所以4n-1里并没有*死空间*，如图 占位.png；即每个空间都有可能用到，只是不动态伸缩数组了而已；
 */
public class SegmentTree_try<E> {

    private E[] tree;
    private E[] data;

    public SegmentTree_try(E[] arr){

        data = (E[])new Object[arr.length];
        for(int i = 0 ; i < arr.length ; i ++)
            data[i] = arr[i];

        tree = (E[])new Object[4 * arr.length];
    }

    public int getSize(){
        return data.length;
    }

    public E get(int index){
        if(index < 0 || index >= data.length)
            throw new IllegalArgumentException("Index is illegal.");
        return data[index];
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
    private int leftChild(int index){
        return 2*index + 1;
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
    private int rightChild(int index){
        return 2*index + 2;
    }
}
